package com.ljc;

import com.ljc.dto.ListNode;
import com.ljc.dto.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author clj
 * @date 2022/11/28
 * @desc 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
 * Given the root of a binary tree, return the inorder traversal of its nodes' values.
 *
 * Example 1:
 * Input: root = [1,null,2,3]
 * Output: [1,3,2]
 *
 * Example 2:
 * Input: root = []
 * Output: []
 *
 * Example 3:
 * Input: root = [1]
 * Output: [1]
 */
public class E94BinaryTreeInorderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        List<Integer> res = inorderTraversal(root);
        System.out.println("inorder: " + res);

        res = preorderTraversal(root);
        System.out.println("preorder: " + res);

        res = postorderTraversal(root);
        System.out.println("postorder: " + res);


    }

    /**
     * 二叉树：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

    /**
     * 二叉树：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }
    public static void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //在二叉树中，前序遍历首先访问根结点然后遍历左子树，最后遍历右子树
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    /**
     * 二叉树：后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    public static void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }

}
